
# class Solution:

    # def letterCombinations(self,digits):
    #     if not digits: return []
    #     phone={
    #         "2":["a","b","c"],
    #         "3":["d","e","f"],
    #         "4":["g","h","i"],
    #         "5":["j","k","l"],
    #         "6":["m","n","o"],
    #         "7":["p","q","r","s"],
    #         "8":["t","u","v"],
    #         "9":["w","x","y","z"]}
    #     def backtrack(conbination,nextdigit):
    #         if len(nextdigit)==0:
    #             res.append(conbination)
    #         else:
    #             for letter in phone[nextdigit[0]]:
    #                 backtrack(conbination+letter,nextdigit[1:])
    #
    #     res=[]
    #     backtrack("",digits)
    #     return res



class Solution:
    def letterCombinations(self, digits) :
        self.dicnum = {2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}
        if len(digits)==0:
            return []
        return self.iter(digits)
    def iter(self,digits):
        rel = []
        if len(digits)==0:
            return ['']
        else:
            i = int(digits[0])
            for j in self.dicnum[i]:
                temp = self.iter(digits[1:])
                for k in temp:
                    rel.append(j+k)
        return rel






s=Solution()
a=s.letterCombinations("23")

print(a)